package leetcode_题库;

import com.sun.org.apache.bcel.internal.generic.ACONST_NULL;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/19 18:30
 */
public class _350_两个数的交集_2 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{4,9,5}, nums2 = new int[]{9,4,9,8,4};

//        System.err.println(Arrays.toString(getIntersection(nums1,nums2)));
        System.err.println(Arrays.toString(getIntersection2(nums1,nums2)));
    }

    private static int[] getIntersection2(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length){
            //确保nums1的长度不超过nums2
            return getIntersection2(nums2,nums1);
        }

        //定义哈希表，存储其中一个数组的信息，默认值可以不给，我给了个大的，哈希表性能应该好一些
        HashMap<Integer,Integer> map = new HashMap<>(nums2.length);
        for (int n : nums2) {
            //存入，getOrderDefault方法是如果n不存在就默认0并获取，不为0就返回，然后再加一
            map.put(n,map.getOrDefault(n,0)+1);
        }
        //临时数组，选的是小的nums数组，这里是nums1，空间小嘛
        int[] temp = new int[nums1.length];
        int index = 0;
        for (int n : nums1) {
            //为啥要map.get(n)>0？这样可以取两数组中的较小数量。
            if (map.containsKey(n) && map.get(n) > 0){
                //存储n，并且让哈希表中该键的数量-1
                temp[index++] = n;
                map.put(n,map.get(n) - 1);
            }
        }
        //此时的数组可能会有无效位0，用性能最好的arraycopy解决
        int[] intersection = new int[index];
        System.arraycopy(temp,0,intersection,0,index);
        return intersection;
        /*
            > 2022/08/19 20:48:54
            解答成功:
                执行耗时:2 ms,击败了96.23% 的Java用户
                内存消耗:41.8 MB,击败了16.87% 的Java用户
         */
    }

    private static int[] getIntersection(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hash1 = new HashMap<>();
        HashMap<Integer,Integer> hash2 = new HashMap<>();

        for(int n:nums1){
            if (hash1.containsKey(n)){
                hash1.put(n,hash1.get(n) + 1);
                continue;
            }
            hash1.put(n,1);
        }
        for(int n:nums2){
            if (hash2.containsKey(n)){
                hash2.put(n,hash2.get(n) + 1);
                continue;
            }
            hash2.put(n,1);
        }

        AtomicInteger index = new AtomicInteger(0);
        int[] intersection = new int[Math.min(nums1.length, nums2.length)];
        hash1.forEach((k,v)->{
            if (hash2.containsKey(k)){
                for (int i = 0; i < Math.min(v,hash2.get(k)); i++) {
                    intersection[index.get()] = k;
                    index.set(index.incrementAndGet());
                }
            }
        });

        if (index.get() == 0){
            return new int[0];
        }else{
            int[] ret = new int[index.get()];
            System.arraycopy(intersection,0,ret,0,index.get());
            return ret;
        }
        /*
            fuck efficiency
            > 2022/08/19 20:16:02
            解答成功:
                执行耗时:4 ms,击败了20.11% 的Java用户
                内存消耗:42 MB,击败了5.05% 的Java用户

         */
    }
}
